package datastructure.sort_algorithm;

import java.util.Arrays;

/**
 * 插入排序
 * 从n开始，将n之前的全部看为一个有序集合，一个一个比较过去并替换
 * O(n^2)
 * @author lbw
 */
public class StraightInsertSort {

    public static void main(String[] args) {
        int[] arr = new int[]{9, 8, -2, 33, -9, 98};

        for (int i = 1; i < arr.length; i++){
            int temp = arr[i];
            int index = i;
            for (int j = i-1; j >= 0 && temp < arr[j]; j--){
                arr[index] = arr[j];
                arr[j] = temp;
                index--;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
